//给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 
//
// 求在该柱状图中，能够勾勒出来的矩形的最大面积。 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入：heights = [2,1,5,6,2,3]
//输出：10
//解释：最大的矩形为图中红色区域，面积为 10
// 
//
// 示例 2： 
//
// 
//
// 
//输入： heights = [2,4]
//输出： 4 
//
// 
//
// 提示： 
//
// 
// 1 <= heights.length <=10⁵ 
// 0 <= heights[i] <= 10⁴ 
// 
//
// Related Topics 栈 数组 单调栈 👍 2552 👎 0


package LeetCode.editor.cn;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author ldltd
 * @date 2023-09-11 17:35:00
 * @description 84.柱状图中最大的矩形
 */
public class LargestRectangleInHistogram{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new LargestRectangleInHistogram().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*暴力，对每个位置中心扩散，向左右查找小于当前位置的边界，然后更新答案
		 * 超时*/
    public int largestRectangleArea1(int[] heights) {
		int l=0,r=0,res=0,t=0;
		for (int i = 0; i < heights.length; i++) {
			l=i;
			for (int j = i-1; l>0&&j>=0 ; j--) {
				if(heights[j]<heights[i]) {
					break;
				}
				l=j;
			}
			r=i;
			for (int j = i+1; j <heights.length ; j++) {
				if(heights[j]<heights[i]) {
					break;
				}
				r=j;
			}
			res=Math.max(res,(r-l+1)*heights[i]);
		}
		return res;
    }

	/*单调栈*/
	public int largestRectangleArea(int[] heights) {
		// 在数组末尾添加一个高度为0的条以处理边界情况
		int[] extendedHeights = new int[heights.length + 2];
		System.arraycopy(heights, 0, extendedHeights, 1, heights.length);
		int res=0;
		Deque<Integer> stack=new LinkedList<>();
		int curr=0;
		while (curr<extendedHeights.length){
			/*对栈中的柱体来说，栈的下一个柱体，
			* 就是其[左边第一个小于自身的柱体]
			* 若当前柱体i的高度小于栈顶高度，
			* 说明i是柱顶[右边第一个小于自身的柱体]
			* 此时左右边界就确定了*/
			while (!stack.isEmpty()&&extendedHeights[curr]<extendedHeights[stack.peek()]){
				int h=extendedHeights[stack.pop()];
				res=Math.max(res,(curr-stack.peek()-1)*h);
			}
			stack.push(curr);
			curr++;
		}
return res;
	}
	public int largestRectangleArea3(int[] heights){
		int res=0;
		int[]hei=new int[heights.length+2];
		System.arraycopy(heights,0,hei,1,heights.length);
		Deque<Integer>stack=new LinkedList<>();
		for (int i = 0; i < hei.length; i++) {
			while (!stack.isEmpty()&&hei[i]<hei[stack.peek()]){
				int h=hei[stack.pop()];
				res=Math.max(res,(i-stack.peek()-1)*h);
			}
			stack.push(i);
		}
		return res;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
